Magic Square Solver (Backtracking Algorithm)ΒΆ
Note
A 3x3 magic square is an arrangement of the numbers from 1 to 9 in a 3 by 3 grid, with each number occurring exactly once, and such that the sum of the entries of any row, any column, or any main diagonal is the same.
Backtracking Algorithm
A backtracking algorithm is a recursive algorithm that attempts to solve a given problem by testing all possible paths towards a solution until a solution is found. Each time a path is tested, if a solution is not found, the algorithm backtracks to test another possible path and so on till a solution is found or all paths have been tested.
The typical scenario where a backtracking algorithm is when you try to find your way out in a maze. Every time you reach a dead-end, you backtrack to try another path untill you find the exit or all path have been explored. Backtracking algorithms can be used for other types of problems such as solving a Magic Square Puzzle or a Sudoku grid.
Backtracking algorithms rely on the use of a recursive function. A recursive function is a function that calls itself until a condition is met.
Note that there are other approaches that could be used to solve the magic square puzzle. The Backtracking approach may not be the most effective but is used in this challenge to demonstrate how a backtracking algorithm behaves and how it can be implemented using Python.
import turtle
from random import randint
from time import sleep
# initialise empty 3 by 3 grid
grid = []
grid.append([8, 0, 0])
grid.append([0, 0, 7])
grid.append([0, 9, 0])
SUM = 15 # Each Row, Column and Diagonal will add up to 15
myPen = turtle.Turtle()
turtle.tracer(0)
myPen.speed(0)
myPen.color("#000000")
myPen.hideturtle()
topLeft_x = -150
topLeft_y = 150
def text(message, x, y, size):
FONT = ('Arial', size, 'normal')
myPen.penup()
myPen.goto(x, y)
myPen.write(message, align="left", font=FONT)
# A procedure to draw the grid on screen using Python Turtle
def drawGrid(grid):
intDim = 100
for row in range(0, 4):
myPen.penup()
myPen.goto(topLeft_x, topLeft_y - row * intDim)
myPen.pendown()
myPen.goto(topLeft_x + 3 * intDim, topLeft_y - row * intDim)
for col in range(0, 4):
myPen.penup()
myPen.goto(topLeft_x + col * intDim, topLeft_y)
myPen.pendown()
myPen.goto(topLeft_x + col * intDim, topLeft_y - 3 * intDim)
for row in range(0, 3):
for col in range(0, 3):
if grid[row][col] != 0:
text(grid[row][col],
topLeft_x + col * intDim + 35,
topLeft_y - row * intDim - intDim + 10,
50)
# A function to check if the grid is a magic square
def checkGrid(grid):
global SUM
for row in range(0, 3):
for col in range(0, 3):
if grid[row][col] == 0:
return False
for row in range(0, 3):
if (grid[row][0] + grid[row][1] + grid[row][2]) != SUM:
return False
for col in range(0, 3):
if (grid[0][col] + grid[1][col] + grid[2][col]) != SUM:
return False
if (grid[0][0] + grid[1][1] + grid[2][2]) != SUM:
return False
if (grid[0][2] + grid[1][1] + grid[2][0]) != SUM:
return False
# We have a magic square!
return True
# A backtracking/recursive function to check all possible
# combinations of numbers until a solution is found
def solveGrid(grid):
# Find next empty cell
for i in range(0, 9):
row = i // 3
col = i % 3
if grid[row][col] == 0:
for value in range(1, 10):
# Can only use numbers that have not been used yet
if not (value in grid[0] or
value in grid[1] or
value in grid[2]):
grid[row][col] = value
# sleep(0.0001)
myPen.clear()
drawGrid(grid)
myPen.getscreen().update()
if checkGrid(grid):
print("Grid Complete and Checked")
return True
else:
if solveGrid(grid):
return True
break
# print("Backtrack")
grid[row][col] = 0
def main():
my_win = turtle.Screen()
drawGrid(grid)
myPen.getscreen().update()
sleep(1)
solved = solveGrid(grid)
if solved:
print("Magic Square Solved")
text("Magic Square Solved", -100, -210, 14)
else:
print("Cannot Solve Magic Square")
text("Cannot Solve Magic Square", -100, -210, 14)
myPen.getscreen().update()
my_win.exitonclick()
if __name__ == "__main__":
main()
mainloop()